home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000013_icon-group-sender _Fri Dec 16 14:44:13 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  2KB
  1. Received: by cheltenham.cs.arizona.edu; Fri, 16 Dec 1994 13:45:52 MST
  2. Date: Fri, 16 Dec 94 14:44:13 CST
  3. From: johnp@utafll.uta.edu (John Paolillo)
  4. Message-Id: <9412162244.AA19530@utafll.uta.edu>
  5. To: icon-group@cs.arizona.edu
  6. Subject: Re: Backtracking
  7. Errors-To: icon-group-errors@cs.arizona.edu
  8.  
  9.  
  10. Dave Kuhlman writes:
  11. >Anyway, I'd be interested to know if others use backtracking
  12. >more heavily, or whether maybe this is just a "neat" but
  13. >not so useful feature of Icon.
  14.  
  15. I have just finished teaching a course "The Computer and Natural Language"
  16. using Icon.  Through this course, Icon's backtracking became  one of my
  17. fondest friends, so to speak.  I do not have the page numbers, but in
  18. the section on pattern matching of Griswold and Griswold, there is
  19. a description of language recognizers and parsers that involves
  20. writing pattern matching functions.  Backtracking is an essential
  21. part of the functioning of such recognizers, and makes it possible 
  22. to teach linguistics students how to write parsers by applying a 
  23. simple translation process to get from a formalism they know:
  24.  
  25.     NP -> (Det) N
  26.  
  27. to something that can actually be used to parse sentences
  28.  
  29.     procedure N()
  30.         suspend ["NP", N()] | ["NP", D(), N()]
  31.     end
  32.  
  33. (note that this is out of context -- it is used inside a scanning 
  34. expression, and it is the backtracking that makes it work)
  35. I have recently tried to implement something similar in another
  36. language that I use (because it is visual), which even employs
  37. failure, but which does not have built-in backtracking.  The result
  38. was an indescribable mess.  I would rank backtracking among the 
  39. most important features of Icon for what I do.  There are many 
  40. many problems you can solve very elegantly with built-in backtracking,
  41. and once you finally understand it, it is hard to live without.
  42.  
  43. BTW, one of my students wrote an Icon program to transcribe Tibetan
  44. in roman transcription into Tibetan orthography, using techniques
  45. exactly like those referred to above.  Tibetan graphemes have different
  46. shapes (i.e. different ascii codes for us) depending on the position
  47. within the syllable that they occur in.  Using a phonotactic parser
  48. that exploits Icon's backtracking allows an elegant solution to this
  49. otherwise difficult problem.
  50.  
  51. John C. Paolillo
  52. Linguistics Program
  53. University of Texas at Arlington